package tum0r.data.structure;

import java.util.ArrayList;
import java.util.List;

/**
 * 工程: JavaTools<br>
 * 包: tum0r.data.structure<br>
 * 创建者: tum0r<br>
 * 创建时间: 2020/8/21 22:22<br>
 * <br>
 */
public class BinaryTree<T> {
    public static final int FRONT = 1000;
    public static final int CENTER = 1001;
    public static final int LAST = 1002;

    private BinaryTree<T> left;
    private BinaryTree<T> right;
    private BinaryTree<T> root;
    private T data;

    public BinaryTree() {
        left = null;
        right = null;
        setData(null);
    }

    public void setData(T data) {
        this.data = data;
    }

    public void setLeftChildren(T data) {
        left = new BinaryTree<>();
        left.setData(data);
        left.root = this;
    }

    public void setRightChildren(T data) {
        right = new BinaryTree<>();
        right.setData(data);
        right.root = this;
    }

    public BinaryTree<T> getLeftChildren() {
        return left;
    }

    public BinaryTree<T> getRightChildren() {
        return right;
    }

    public BinaryTree<T> getRoot() {
        return root;
    }

    public T getData() {
        return data;
    }

    public List<T> frontSequence() {
        return getSequence(this,FRONT);
    }

    public List<T> centerSequence() {
        return getSequence(this, CENTER);
    }

    public List<T> lastSequence() {
        return getSequence(this, LAST);
    }

    private List<T> getSequence(BinaryTree<T> root, int type) {
        List<T> result = new ArrayList<>();
        BinaryTree<T> tempLeft = root.getLeftChildren();
        BinaryTree<T> tempRight = root.getRightChildren();
        if (type == FRONT) {
            result.add(root.getData());
        }
        if (tempLeft!=null&&tempLeft.getData() != null) {
            result.addAll(getSequence(tempLeft, type));
        }
        if (type == CENTER) {
            result.add(root.getData());
        }
        if (tempRight!=null&&tempRight.getData() != null) {
            result.addAll(getSequence(tempRight, type));
        }
        if (type == LAST) {
            result.add(root.getData());
        }
        return result;
    }

    public int deep() {
        return getDeep(this);
    }

    private int getDeep(BinaryTree<T> root) {
        int length = 1;
        int leftLength = 0;
        int rightLength = 0;
        if (root.getLeftChildren() != null) {
            leftLength += getDeep(root.getLeftChildren());
        }
        if (root.getRightChildren() != null) {
            rightLength += getDeep(root.getRightChildren());
        }
        length += Math.max(leftLength, rightLength);
        return length;
    }

    public BinaryTree<T> copy() {
        BinaryTree<T> copy = new BinaryTree<>();
        copy(this, copy);
        return copy;
    }

    private void copy(BinaryTree<T> root, BinaryTree<T> copy) {
        copy.setData(root.getData());
        BinaryTree<T> left = root.getLeftChildren();
        BinaryTree<T> right = root.getRightChildren();
        if (left != null) {
            copy.setLeftChildren(null);
            copy(left, copy.getLeftChildren());
        }
        if (right != null) {
            copy.setRightChildren(null);
            copy(right, copy.getRightChildren());
        }
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof BinaryTree && this.deep() == ((BinaryTree<T>) obj).deep()) {
            return equals(this, (BinaryTree<T>) obj);
        }
        return false;
    }

    private boolean equals(BinaryTree<T> binaryTree1, BinaryTree<T> binaryTree2) {
        boolean equals = true;
        if (binaryTree1 != null) {
            if (binaryTree1.equals(binaryTree2.getData())) {
                equals = equals(binaryTree1.getLeftChildren(), binaryTree2.getLeftChildren());
                if (!equals) {
                    return false;
                }
                equals = equals(binaryTree1.getRightChildren(), binaryTree2.getRightChildren());
            } else {
                equals = false;
            }
        } else if (binaryTree2 != null) {
            if (binaryTree2.equals(binaryTree1.getData())) {
                equals = equals(binaryTree1.getLeftChildren(), binaryTree2.getLeftChildren());
                if (!equals) {
                    return false;
                }
                equals = equals(binaryTree1.getRightChildren(), binaryTree2.getRightChildren());
            } else {
                equals = false;
            }
        }
        return equals;
    }
}
